import java.util.HashMap;
import java.util.Map;
import java.util.Stack;

/**
 * @author Sebastian
 * @version 2.0
 * @date 2024/7/30 10:51
 */
// 基本计算器(考虑括号)
    // https://leetcode.cn/problems/basic-calculator/description/
public class Solution224 {
    Map<Character, Integer> map = new HashMap<Character, Integer>();
    public Solution224() {
        map.put('-', 1);
        map.put('+', 1);
        map.put('*', 2);
        map.put('/', 2);
        map.put('%', 2);
        map.put('^', 3);
    }
    Stack<Integer> nums = new Stack<Integer>();
    Stack<Character> ops = new Stack<Character>();
    public int calculate(String s) {
        s = s.replaceAll(" ", "");
        int len = s.length();
        for (int i = 0; i < len; i++) {
            char c = s.charAt(i);
            if (c == '(') {
                ops.push(c);
            } else if (c == ')') {
                while (ops.peek() != '(') {
                    applyOps();
                }
                // 弹出左括号，因为题目保证算式一定有效
                ops.pop();
            } else if (Character.isDigit(c)) {
                int num = 0;
                // 整体取出i开始的连续数字
                int tmp = i;
                while (tmp < len && Character.isDigit(s.charAt(tmp))) {
                    num = num * 10 + (s.charAt(tmp) - '0');
                    tmp++;
                }
                nums.push(num);
                i = tmp - 1;
            } else { //处理操作符
                //s =
                //"1-(     -2)"
                if (i == 0 && c == '-' || i > 0 && s.charAt(i - 1) == '(') {
                    nums.push(0);
                }
                // 当有一个新操作入栈，先算栈内
                while (!ops.isEmpty() && ops.peek() != '(') {
                    char peek = ops.peek();
                    // 栈内运算符优先级大于或等于当前运算符
                    if (map.get(peek) >= map.get(c)) {
                        applyOps();
                    } else {
                        break;
                    }
                }
                ops.push(c);
            }
        }
        while (!ops.isEmpty()){
            applyOps();
        }
        return nums.peek();
    }

    // 计算两个操作数的结果
    public void applyOps() {
        if (nums.size() < 2 || ops.isEmpty()){
            return;
        }
        int b = nums.pop(), a = nums.pop();
        char op = ops.pop();
        int res = 0;
        if (op == '+')
            res = a + b;
        else if (op == '-')
            res = a - b;
        else if (op == '*')
            res = a * b;
        else if (op == '/')
            res = a / b;
        else if (op == '^')
            res = (int)Math.pow(a, b);
        else if (op == '%')
            res = a % b;
        nums.push(res);
    }
}
